Search for: All records

Abstract Given two k -graphs ( k -uniform hypergraphs) F and H , a perfect F -tiling (or F -factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H . For all complete k -partite k -graphs K , Mycroft proved a minimum codegree condition that guarantees a K -factor in an n -vertex k -graph, which is tight up to an error term o ( n ). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K (k) (1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively. 

Promising for digital signal processing applications, approximate computing has been extensively considered to tradeoff limited accuracy for improvements in other circuit metrics such as area, power, and performance. In this paper, approximate arithmetic circuits are proposed by using emerging nanoscale spintronic devices. Leveraging the intrinsic current-mode thresholding operation of spintronic devices, we initially present a hybrid spin-CMOS majority gate design based on a composite spintronic device structure consisting of a magnetic domain wall motion stripe and a magnetic tunnel junction. We further propose a compact and energy-efficient accuracy-configurable adder design based on the majority gate. Unlike most previous approximate circuit designs that hardwire a constant degree of approximation, this design is adaptive to the inherent resilience in various applications to different degrees of accuracy. Subsequently, we propose two new approximate compressors for utilization in fast multiplier designs. The device-circuit SPICE simulation shows 34.58% and 66% improvement in power consumption, respectively, for the accurate and approximate modes of the accuracy-configurable adder, compared to the recently reported domain wall motion-based full adder design. In addition, the proposed accuracy-configurable adder and approximate compressors can be efficiently utilized in the discrete cosine transform (DCT) as a widely-used digital image processing algorithm. The results indicate that the DCT and inverse DCT (IDCT) using the approximate multiplier achieve ~2x energy saving and 3x speed-up compared to an exactly-designed circuit, while achieving comparable quality in its output result. 

For and , let be a ‐partite ‐graph with parts each of size , where is sufficiently large. Assume that for each , every ‐set in lies in at least edges, and . We show that if , then contains a matching of size . In particular, contains a matching of size if each crossing ‐set lies in at least edges, or each crossing ‐set lies in at least edges and . This special case answers a question of Rödl and Ruciński and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases.

 

Since the late 19^thcentury, enormous endeavors have been made in extending the scope and capability of optical interferometers. Recently, plasmonic vortices that strongly confine the orbital angular momentum to surface have attracted considerable attention. However, current research interests in this area have focused on the mechanisms and dynamics of polarization‐dependent single plasmonic vortex generation and evolution, while the interference between different plasmonic vortices for practical applications has been unexplored. Here, a method for flexible on‐chip spin‐to‐orbital angular momentum conversion is introduced, resulting in exotic interferograms. Based on this method, a new form of interferometers that is realized by the interference between customized plasmonic vortices is demonstrated. Within wavelength‐scale dimension, the proposed plasmonic vortex interferometers exhibit superior performance to directly measure the polarization state, spin and orbital angular momentum of incident beams. The proposed interferometry is straightforward and robust, and can be expected to be applied to different scenarios, fueling fundamental advances and applications alike.